{
LANG : PASCAL
PROB : inflate
}

program INFLATE;
const
  fi = 'inflate.in';
  fo = 'inflate.out';
  max = 10000;
type
  cat = record
          worth, minute : integer;
          v : real;
        end;
var
  a : array[1..max] of cat;
  d : array[0..1, 0..max] of longint;
  m, n, res : longint;
  tren, duoi : byte;

procedure inp;
var
  i : longint;
begin
  read(m, n);
  for i := 1 to n do
    with a[i] do
    begin
      read(worth, minute);
      v := worth/minute;
    end;
end;

function max2(x, y : longint) : longint;
begin
  if x > y then max2 := x
  else max2 := y;
end;

procedure process1;
var
  i, j : longint;
begin
  fillchar(d, sizeof(d), 0);
  tren := 0;
  duoi := 1;
  for i := 1 to n do
    with a[i] do
    begin
      for j := 0 to m do
      begin
        d[duoi, j] := d[tren, j];
        if (j >= 1) and (d[duoi, j] < d[duoi, j-1]) then d[duoi, j] := d[duoi, j-1];
        if (j >= minute) and (d[duoi, j] < d[duoi, j-minute] + worth) then
          d[duoi, j] := d[duoi, j-minute] + worth;
      end;
      tren := duoi;
      duoi := duoi xor 1;
    end;
  for j := m downto 0 do
    if d[tren, j] > 0 then
    begin
      res := d[tren, j];
      break;
    end;
end;

procedure swap(i, j : longint);
var
  temp : cat;
begin
  temp := a[i];
  a[i] := a[j];
  a[j] := temp;
end;

procedure sort(l, r : longint);
var
  i, j : longint;
  k : real;
begin
  if l >= r then exit;
  i := l;
  j := r;
  k := a[l+random(r-l+1)].v;
  repeat
    while a[i].v > k do inc(i);
    while a[j].v < k do dec(j);
    if i <= j then
    begin
      swap(i, j);
      inc(i); dec(j);
    end;
  until i > j;
  sort(i, r); sort(l, j);
end;

procedure process2;
var
  i : longint;
begin
  sort(1, n);
  res := 0;
  for i := 1 to n do
    with a[i] do
      if m > minute then
      begin
        inc(res, (m div minute)*worth);
        m := m mod minute;
      end;
end;

begin
  assign(input, fi); reset(input);
  assign(output, fo); rewrite(output);
  inp;
  if m*n <= 1000000 then process1
  else process2;
  writeln(res);
  close(output);
  close(input);
end.